package com.lans.alg;

import java.util.Arrays;

/**
 * @author: lans
 * @date: 2025/3/11
 * @name: 刘宇
 */
public class MinTree {

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F','G'};
        int verxs = data.length;
        int[][] weight = {
                {10000,5,7,10000,10000,10000,2}, //A
                {5,10000,10000,9,10000,10000,3}, //B
                {7,10000,10000,10000,8,10000,10000}, //C
                {10000,9,10000,10000,10000,4,10000}, //D
                {10000,10000,8,10000,10000,5,4}, //E
                {10000,10000,10000,4,5,10000,6}, //F
                {2,3,10000,10000,4,6,10000}};//G
        MGraph mGraph = new MGraph(verxs);
        createGraph(mGraph,verxs,data,weight);
        lineGraph(mGraph);
        prim(mGraph,1);
    }

    /**
     *
     * @param graph 图
     * @param v 从哪个顶点开始计算 0表示从A开始
     */
    public static void prim(MGraph graph,int v){
        //判断标记的节点是否被访问过 0/1 no/yes
        int[] visited = new int[graph.verxs];
        visited[v]=1;//表示已经访问过
        int minWeight = 10000;

        int h1=-1;
        int h2=-1;
        for(int k=0;k<graph.verxs-1;k++){//遍历每一条边 n-1

            for(int i=0;i<graph.verxs;i++){//访问邻接数组中的每一个元素
                for(int j=0;j<graph.verxs;j++){
                    if(visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
                        //说明i已经被找过 j没有找到 此时就去找i到j的距离最短 i到j最短距离记录下来
                        minWeight = graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            //找到最小的一条边
            System.out.println("边"+graph.data[h1]+" , "+graph.data[h2]+" 权值: "+minWeight);
            visited[h2]=1;
            minWeight = 10000;
        }
    }



    public static void createGraph(MGraph graph,int verxs,char[] data,int[][]weight) {
        int i,j;
        for(i=0;i<verxs;i++){
            graph.data[i]=data[i];
            for(j=0;j<verxs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }

    public static void lineGraph(MGraph graph){
        for(int[] i:graph.weight){
            System.out.println(Arrays.toString(i));
        }
    }

}

class MGraph{

    //图的节点数
    int verxs;

    //存放节点数
    char[] data;

    //邻接矩阵,用来表示顶点和顶点之间边的距离
    int[][] weight;

    public MGraph(int verxs){
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}